package BackTracking.chessboard;//n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
//
// 给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。 
//
// 
//
// 
// 
// 示例 1： 
//
// 
//输入：n = 4
//输出：2
//解释：如上图所示，4 皇后问题存在两个不同的解法。
// 
//
// 示例 2： 
//
// 
//输入：n = 1
//输出：1
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 9 
// 皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。 
// 
// 
// 
// Related Topics 回溯 👍 315 👎 0


import java.util.Arrays;

//leetcode submit region begin(Prohibit modification and deletion)
class totalNQueensI {
    int sum = 0;
    public int totalNQueens(int n) {

        char[][] chessboard = new char[n][n];
        for (char[] c : chessboard) {
            Arrays.fill(c, '.');
        }
        backTrack(chessboard,n,0);
        return sum;

    }

    private void backTrack(char[][] chessboard, int n, int row){
        //n皇后取的是叶子节点
        if(row==n){
            sum++;
        }
        for (int i = 0; i < n; i++) {
            if(isValid(row,i,chessboard,n)){
                chessboard[row][i] = 'Q';
                backTrack(chessboard, n, row+1);
                chessboard[row][i] = '.';
            }
        }
    }

    private boolean isValid(int row, int col, char[][] chessboard, int n){
//        因为在单层搜索的过程中，每一层递归，只会选for循环（也就是同一行）里的一个元素，所以不用去重行了。
        //检查一列上有没有
        for (int i = 0; i < n; i++) {
            if(chessboard[i][col]=='Q'){
                return false;
            }
        }
        //检查左上对角线有没
        for (int i=col-1,j=row-1; i>=0&&j>=0; j--,i--){
            if(chessboard[j][i]=='Q'){
                return false;
            }
        }
        //检查右上对角线有没
        for (int i = col+1,j=row-1; i <= n-1 && j>=0 ; i++,j--) {
            if (chessboard[j][i] == 'Q') {
                return false;
            }
        }
        return true;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
